package day190812;

import java.util.ArrayList;
import java.util.List;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/12 下午 03:09
 */
public class SolveNQueens {

    private List<List<String>> results = new ArrayList<>();
    private int solveNum = 0;
    private int queenNum;

    private int[] result;// 全局或成员变量, 下标表示行, 值表示 queen 存储在哪一列

    public List<List<String>> solveNQueens(int n) {
        queenNum = n;
        result = new int[queenNum];
        cal8queens(0);
        return results;
    }

    public void cal8queens(int row) { // 调用方式：cal8queens(0);
        if (row == queenNum) { // 8 个棋子都放置好了，打印结果
            printQueens(result);
            return; // 8 行棋子都放好了，已经没法再往下递归了，所以就 return
        }
        for (int column = 0; column < queenNum; ++column) { // 每一行都有 8 中放法
            if (isOk(row, column)) { // 有些放法不满足要求
                result[row] = column; // 第 row 行的棋子放到了 column 列
                cal8queens(row + 1); // 考察下一行
            }
        }
    }

    private boolean isOk(int row, int column) {// 判断 row 行 column 列放置是否合适
        int leftup = column - 1, rightup = column + 1;
        for (int i = row - 1; i >= 0; --i) { // 逐行往上考察每一行
            if (result[i] == column) {
                return false; // 第 i 行的 column 列有棋子吗？
            }
            if (leftup >= 0) { // 考察左上对角线：第 i 行 leftup 列有棋子吗？
                if (result[i] == leftup) {
                    return false;
                }
            }
            if (rightup < queenNum) { // 考察右上对角线：第 i 行 rightup 列有棋子吗？
                if (result[i] == rightup) {
                    return false;
                }
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

    private void printQueens(int[] result) { // 打印出一个二维矩阵
        List<String> list = new ArrayList<>();
        for (int row = 0; row < queenNum; ++row) {
            if (list.size() >= queenNum) {
                list = new ArrayList<>();
            }
            StringBuilder builder = new StringBuilder();
            for (int column = 0; column < queenNum; ++column) {
                if (result[row] == column) {
                    System.out.print("Q ");
                    builder.append("Q");
                } else {
                    System.out.print("* ");
                    builder.append(".");
                }
            }
            list.add(builder.toString());
        }
        results.add(list);
        solveNum ++ ;
    }

    public int totalNQueens(int n) {
        queenNum = n;
        result = new int[queenNum];
        cal8queens(0);
        return solveNum;
    }

    public static void main(String[] args) {
        SolveNQueens solveNQueens = new SolveNQueens();

//        solveNQueens.solveNQueens(4);
//        int totalNQueens = solveNQueens.totalNQueens(4);
        boolean aab = solveNQueens.isMatch("ab", ".*");
        return;
    }

    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean firstMatch = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        if (p.length() >= 2 && p.charAt(1) == '*'){
            return (isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p)));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
    private boolean matched = false;
    private char[] pattern; // 正则表达式
    private int plen; // 正则表达式长度

    public void Pattern(char[] pattern, int plen) {
        this.pattern = pattern;
        this.plen = plen;
    }

    public boolean match(char[] text, int tlen) { // 文本串及长度
        matched = false;
        rmatch(0, 0, text, tlen);
        return matched;
    }

    private void rmatch(int ti, int pj, char[] text, int tlen) {
        if (matched) return; // 如果已经匹配了，就不要继续递归了
        if (pj == plen) { // 正则表达式到结尾了
            if (ti == tlen) matched = true; // 文本串也到结尾了
            return;
        }
        if (pattern[pj] == '*') { // * 匹配任意个字符

            for (int k = 1; k <= tlen-ti; ++k) {
                if (ti + k >= tlen || pj - 1 >= tlen) {
                    rmatch(ti+k, pj+1, text, tlen);
                    break;
                }
                if ((pattern[pj - 1] == '.' && text[pj - 1] != text[ti + k]) && pattern[pj - 1] != text[ti + k]) {
                    rmatch(ti+k, pj+1, text, tlen);
                    break;
                }
            }
        } else if (pattern[pj] == '.') { // ? 匹配 0 个或者 1 个字符
            rmatch(ti, pj+1, text, tlen);
            rmatch(ti+1, pj+1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
            rmatch(ti+1, pj+1, text, tlen);
        } else {
            rmatch(ti, pj + 1, text, tlen);
        }
    }



}
